A New Fully Polynomial Time Approximation Scheme for the Interval Subset Sum Problem

摘要

The interval subset sum problem (ISSP) is a generalization of the well-knownsubset sum problem. Given a set of intervals$\left\{[a_{i,1},a_{i,2}]\right\}_{i=1}^n$ and a target integer $T,$ the ISSPis to find a set of integers, at most one from each interval, such that theirsum best approximates the target $T$ but cannot exceed it. In this paper, wefirst study the computational complexity of the ISSP. We show that the ISSP isrelatively easy to solve compared to the 0-1 Knapsack problem (KP). We alsoidentify several subclasses of the ISSP which are polynomial time solvable(with high probability), albeit the problem is generally NP-hard. Then, wepropose a new fully polynomial time approximation scheme (FPTAS) for solvingthe general ISSP problem. The time and space complexities of the proposedscheme are ${\cal O}\left(n \max\left\{1 / \epsilon,\log n\right\}\right)$ and${\cal O}\left(n+1/\epsilon\right),$ respectively, where $\epsilon$ is therelative approximation error. To the best of our knowledge, the proposed schemehas almost the same time complexity but a significantly lower space complexitycompared to the best known scheme. Both the correctness and efficiency of theproposed scheme are validated by numerical simulations. In particular, theproposed scheme successfully solves ISSP instances with $n=100,000$ and$\epsilon=0.1\%$ within one second.